Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського»  ЗВІТ до лабораторної роботи № 2 з дисципліни «Програмування складних алгоритмів» Тема «Рекурсивні алгоритми» Варіант № 11                             Лабораторна робота № 1: Рекурсивні алгоритми Мета: набуття практичних навичок з рекурсивними функціями. Завдання до лабораторної роботи Розробити програми згідно з алгоритмом з використанням рекурсивної функції та без використання рекурсивної функції. Оцінити час виконання та складність алгоритму. Завдання відповідно до варіанту: / Теоретичні відомості Рекурсія – це побудова методу таким чином, що він викликає сам себе. Рекурсивні виклики методу мають завершуватись при досягненні деякої умови. В іншому випадку відбудеться переповнення пам’яті і програма “зависне” не досягнувши обчислення необхідного результату. Рекурсивний метод – це метод, який сам себе викликає. У рекурсивному методі міститься виклик цього ж методу за його іменем. Послідовний процес рекурсивних викликів методу є подібний до циклічного процесу. Як працює рекурсивний виклик методу? Якщо метод викликає сам себе, то в пам’яті відбуваються наступні процеси: в системному стеку виділяється пам’ять для нових локальних змінних і параметрів; програмний код методу виконується з початку з новими локальними змінними і параметрами. Ці локальні змінні та параметри отримують нові початкові значення. Самий програмний код методу не копіюється; при поверненні з рекурсивного методу відбувається відновлення старих локальних змінних та параметрів а також їх значень у точці виклику цього методу. Рекурсія завжди порівнюється з ітерацією. Для багатьох задач, рекурсія дає наступні взаємопов’язані переваги: при виклику рекурсивної функції не потрібно додатково зберігати тимчасові значення локальних змінних. Компілятор будує код рекурсивної функції таким чином, що тимчасові значення локальних змінних автоматично зберігаються при кожному рекурсивному виклику; у деяких випадках рекурсивні алгоритми виглядають більш спрощено та більш наочно ніж ітераційні. Це пов’язано з тим, що в ітераційних алгоритмах для запам’ятовування проміжних результатів потрібно вводити додаткові змінні, які можуть ускладнити сприйняття ходу виконання самого алгоритму. Порівняно з ітераційними викликами, побудова рекурсивних викликів має такі недоліки: для заданого алгоритму рекурсивні виклики працюють повільніше ніж ітераційні. Це пов’язано з додатковими затратами системних ресурсів на неодноразові виклики методів; багаторазовий виклик методів може призвести до переповнення системного стеку. У цьому випадку середовище CLR згенерує відповідну виключну ситуацію. Тому, важливо, щоб рекурсивний метод був розроблений таким чином, щоб в ньому оголошувалась мінімально можлива кількість параметрів та локальних змінних. Приклад 1. Використання рекурсії для обчислення факторіала числа: int factorial(int i) {   if (i==0) return 1;   else return i*factorial(i-1); } Приклад 2. Приклад обчислення суми ряду: int S(int n) { if (n == 1)     return 5;     else         return 5 * n + S(n - 1); } Результати роботи Без рекурсивної функції: З клавіатури задаємо граничне значення n. Умовним оператором if() перевіряємо це число. Воно має бути більшим 0. Тепер за допомогою циклу for() рахуємо добуток ряду. Обчислюємо часову складність алгоритму. З використанням рекурсивної функції: З клавіатури задаємо граничне значення n. Умовним оператором if() перевіряємо це число. Воно має бути більшим 0. Створюємо функцію func() і передаємо значення n. Рахуємо добуток ряду. У головній функції main() викликаємо func(). Обчислюємо часову складність алгоритму. n Складність Час алгоритму  Без рекурсії 10  O(n) 2.169* 10 −5   20  2.555* 10 −5   50  3.21* 10 −5  З рекурсією 10  2.721* 10 −5   20  2.803* 10 −5   50  3.526* 10 −5   1.4. Лістинг програми та результати роботи Без рекурсії: #include <iostream> #include <cm...